﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Digraphs
{
    public class KosarajuCC
    {
        private bool[] marked;//已访问的顶点
        private int[] id;//强连通分量的标识符
        private int count;//强连通分量的数量

        public KosarajuCC(Digraph G)
        {
            marked = new bool[G.V()];
            id = new int[G.V()];
            DepthFirstOrder order = new DepthFirstOrder(G.Reverse());
            foreach (var s in order.ReversePost())
            {
                if (!marked[s])
                {
                    Dfs(G,s);
                    count++;
                }
            }
        }

        private void Dfs(Digraph G, int v)
        {
            marked[v] = true;
            id[v] = count;
            foreach (var w in G.Adj(v))
            {
                if (!marked[w])
                    Dfs(G,w);
            }
        }

        public bool StronglyConnected(int v, int w)
        {
            return id[v] == id[w];
        }

        public int Id(int v)
        {
            return id[v];
        }

        public int Count()
        {
            return count;
        }
    }
}
